#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read<int>()
#define lin read<ll>()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

template <typename T>
T read(){
	T x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

inline ll mul(ll x,ll y,ll mod){return (__int128) x * y % mod;}

inline ll qp(ll x,ll t,ll mod){ll res=1;for(;t;t>>=1,x=mul(x,x,mod))if(t&1)res=mul(res,x,mod);return res;}

bool miller_rabin(ll n,ll a){
	ll d = n-1,r = 0;
	while(!(d & 1)) d >>= 1,r++;
	ll x = qp(a,d,n); if(x == 1) return 1;
	for(int i = 0;i < r;i++){
		if(x == n-1) return 1;
		x = mul(x,x,n);
	}return 0;
}

bool isprime(ll x){
	if(x < 2) return 0;
	int prime_table[8] = {2,3,5,11,13,23,31,37};
	for(int i = 0;i < 8;i++){
		if(x == prime_table[i]) return 1;
		if(!miller_rabin(x,prime_table[i])) return 0;
	}return 1;
}

ll random(ll mod){return 1ll * rand() * rand() % mod;}

inline ll f(ll x,ll c,ll mod){return (mul(x,x,mod) + c) % mod;}

inline ll gcd(ll x,ll y){return !y ? x : gcd(y,x%y);}

ll maxfac;

ll pollard_rho(ll n){
	ll c = random(n-1) + 1;
	ll v1 = 0;
	for(int s = 1,t = 2;;s <<= 1,t <<= 1){
		ll v2 = v1,pro = 1;
		for(int i = s,cnt = 1;i < t;i++,cnt++){
			v2 = f(v2,c,n);
			pro = mul(pro,abs(v2-v1),n);
			if(cnt == 127){
				cnt = 0;
				ll v = gcd(pro,n);
				if(v > 1) return v;
			}
		}
		ll v = gcd(pro,n);
		if(v > 1) return v;
		v1 = v2;
	}return n;
}

void factorize(ll n){
	if(isprime(n)) return maxfac = max(maxfac,n),void();
	if(n < 2 || n <= maxfac) return;
	ll g = n;
	while(g == n) g = pollard_rho(n);
	factorize(n/g); factorize(g);
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	int t = in;
	while(t--){
		maxfac = 0; ll x = lin;
		factorize(x);
		if(maxfac == x) puts("Prime");
		else printf("%lld\n",maxfac);
	}
	return 0;
}

